using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace QuadTreeExample
{
    class QuadTree
    {
        QTNode root;

        internal QTNode Root
        {
            get { return root; }
            set { root = value; }
        }

        int width;
        int height;
        int maxDepth;

        public int Width
        {
            get { return width; }
            set { width = value; }
        }
        public int Height
        {
            get { return height; }
            set { height = value; }
        }

        public QuadTree(int widthIn, int heightIn, int maxDepthIn)
        {
            width = widthIn;
            height = heightIn;
            maxDepth = maxDepthIn;


            root = new QTNode(0, width, 0, height, "Root-");
        }


        public void PutInTree(double xIn, double yIn, object objIn)
        {
            NodeData dataIn = new NodeData();
            dataIn.Data = objIn;
            dataIn.X = xIn;
            dataIn.Y = yIn;

            bool done = false;
            QTNode currNode = root;
            while (!done)
            {
                if (currNode.HasChildren)
                {
                    currNode = GetContainingChildNode(currNode, dataIn);
                }
                else
                {
                    //current node has data
                    if (currNode.Data != null)
                    {
                        //if we're not at the max depth
                        if (currNode.Depth < maxDepth)
                        {
                            //partition the current node into 4 
                            currNode.Partition();


                            //hold onto the data at this node
                            List<NodeData> oldData = currNode.Data;
                            if (oldData.Count > 1)
                            {
                                throw new Exception("multiple data at a non-leaf node");
                            }


                            //place the old data back into the tree
                            QTNode temp;
                            temp = GetContainingChildNode(currNode, oldData[0]);
                            temp.Data = oldData;


                            currNode.Data = null;


                            /*
                            temp = GetContainingChildNode(currNode, locationIn);
                            temp.Data = dataIn;
                            temp.Location = locationIn;
                            */
                        }
                        else
                        {
                            currNode.Data.Add(dataIn);
                            done = true;
                        }
                    }
                    else
                    {
                        //place dataIn in the current node
                        currNode.Data = new List<NodeData>();
                        currNode.Data.Add(dataIn);
                        done = true;
                    }
                }




            }

        }

        /// <summary>
        /// Find the child node of the input node
        /// that contains the input location
        /// </summary>
        /// <param name="currNode"></param>
        /// <param name="locationIn"></param>
        /// <returns></returns>
        private QTNode GetContainingChildNode(QTNode currNode, NodeData dataIn)
        {
            QTNode node = null;
            bool done = false;
            int i = 0;
            while (!done && i < 4)
            {
                if (dataIn.X < currNode.Children[i].XMax && dataIn.X >= currNode.Children[i].XMin
                    && dataIn.Y < currNode.Children[i].YMax && dataIn.Y >= currNode.Children[i].YMin)
                {
                    done = true;
                    node = currNode.Children[i];
                }

                i++;
            }

            if (node == null)
            {
                throw new Exception("location not contained in child nodes!");
            }
            return node;

        }


        internal List<QTNode> GetNodesContainedBy(double xMinIn, double xMaxIn, double yMinIn, double yMaxIn)
        {





        }

        internal QTNode GetNodeContaining(double xIn, double yIn)
        {
            NodeData dataIn = new NodeData();
            dataIn.X = xIn;
            dataIn.Y = yIn;
            QTNode currNode = root;
            while (currNode.HasChildren)
            {
                currNode = GetContainingChildNode(currNode, dataIn);
            }
            return currNode;
            /*
            Rectangle tempRect = new Rectangle();
            tempRect.X = (int)currNode.XMin;
            tempRect.Y = (int)currNode.YMin;
            tempRect.Width = (int)(currNode.XMax - tempRect.X);
            tempRect.Height = (int)(currNode.YMax - tempRect.Y);

            return tempRect;
             */
        }
    }
}
